package cn.xaut.查找表;

import java.util.*;

public class demo49 {
    
    // 计数
    public List<List<String>> groupAnagrams3(String[] strs) {

        if (strs.length == 0)
            return new ArrayList<>();

        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            
            int[] count = new int[26];
            for (char c : s.toCharArray()) 
                count[c - 'a'] ++;
            
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append("#");
                sb.append(count[i]);
            }
            
            if (!map.containsKey(sb.toString()))
                map.put(sb.toString(), new ArrayList<>());
            map.get(sb.toString()).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
    
    // 第二次尝试
    // 散列表
    // 字母排序
    public List<List<String>> groupAnagrams2(String[] strs) {
    
        if (strs.length == 0)
            return new ArrayList<>();

        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);
            String key = String.valueOf(cs);
            if (!map.containsKey(key))
                map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }

        return new ArrayList<>(map.values());
    }
    
    private boolean isAnagrams(String s, String t) {
        
        if (s.length() != t.length())
            return false;
        
        char[] cs = s.toCharArray();
        char[] ts = t.toCharArray();

        int[] freq = new int[26];
        for (char c : cs) 
            freq[c - 'a'] ++;

        for (char c : ts) {
            freq[c - 'a'] --;
            if (freq[c - 'a'] < 0)
                return false;
        }
        
        return true;
    }
    
    // 错误的解法
    public List<List<String>> groupAnagrams(String[] strs) {

        List<List<String>> res = new ArrayList<>();

//        List<String> list = Arrays.asList(strs);

        for (int i = 0; i < strs.length; i++) {
            List<String> list = new ArrayList<>();
            list.add(strs[i]);
            for (int j = i + 1; j < strs.length; j++) {
                if (isAnagrams(strs[i], strs[j]))
                    list.add(strs[j]);
            }
            res.add(list);
        }
        
        return res;
    }

    public static void main(String[] args) {

        List<List<String>> res = new demo49().groupAnagrams3(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        for (List<String> list : res)
            System.out.println(list);   
/*      [
          ["ate","eat","tea"],
          ["nat","tan"],
          ["bat"]
        ]
        */
    }
}
